The present invention relates to computer animation. More specifically, the present invention relates to methods and apparatus for dynamically determining models for computer animation.
Throughout the years, movie makers have often tried to tell stories involving make-believe creatures, far away places, and fantastic things. To do so, they have often relied on animation techniques to bring the make-believe to “life.” Two of the major paths in animation have traditionally included, drawing-based animation techniques and stop motion animation techniques.
Drawing-based animation techniques were refined in the twentieth century, by movie makers such as Walt Disney and used in movies such as “Snow White and the Seven Dwarfs” (1937) and “Fantasia” (1940). This animation technique typically required artists to hand-draw (or paint) animated images onto a transparent media or cels. After painting, each cel would then be captured or recorded onto film as one or more frames in a movie.
Stop motion-based animation techniques typically required the construction of miniature sets, props, and characters. The filmmakers would construct the sets, add props, and position the miniature characters in a pose. After the animator was happy with how everything was arranged, one or more frames of film would be taken of that specific arrangement. Stop motion animation techniques were developed by movie makers such as Willis O'Brien for movies such as “King Kong” (1933). Subsequently, these techniques were refined by animators such as Ray Harryhausen for movies including “Mighty Joe Young” (1948) and Clash Of The Titans (1981).
With the wide-spread availability of computers in the later part of the twentieth century, animators began to rely upon computers to assist in the animation process. This included using computers to facilitate drawing-based animation, for example, by painting images, by generating in-between images (“tweening”), and the like. This also included using computers to augment stop motion animation techniques. For example, physical models could be represented by virtual models in computer memory, and manipulated.
One of the pioneering companies in the computer-aided animation (CA) industry was Pixar. Pixar is more widely known as Pixar Animation Studios, the creators of animated features such as “Toy Story” (1995) and “Toy Story 2” (1999), “A Bugs Life” (1998), “Monsters, Inc.” (2001), “Finding Nemo” (2003), “The Incredibles” (2004), “Cars” (2006) and others. In addition to creating animated features, Pixar developed computing platforms specially designed for CA, and CA software now known as RenderMan®. RenderMan® was particularly well received in the animation industry and recognized with two Academy Awards®. The RenderMan® software included a “rendering engine” that “rendered” or converted geometric and/or mathematical descriptions of objects into a two dimensional image. The named inventor of the present invention co-developed the original RenderMan® software.
The inventor of the present invention has recognized that reducing rendering time is very important for computer animation. The rendering process can be a time consuming operation that may take hours, if not days, when rendering an image with many objects. As an example, if a scene included ten thousand plants, each with a million leaves, the rendering engine would have to process ten billion leaves in the scene. Accordingly, the time to render such a scene would be unacceptably long and would require massive amounts of memory. Multiplying this rendering time by the number of frames (e.g. 130,000) in a typical feature-length animated feature images results in a rendering time that is impractical.
One technique developed by Pixar engineers to reduce rendering time, and not in the prior art, has been to reconfigure the rendering pipeline. The current RenderMan® software is based upon a “bucket” by “bucket” rendering engine architecture, where images are rendered one at a time. In U.S. application Ser. No. 10/428,325, filed Apr. 30, 2003, Pixar discloses a new and pioneering rendering engine architecture where objects are rendered for a “shot” of images at a time. By using such an architecture, the rendering times for a shot of images is greatly reduced because objects are retrieved from a disk once, for a series of images in the shot. Other advantages are also discussed in that application.
Another technique considered to attempt to reduce the rendering time has been through the manual definition and use of distinctly different level of detail (LOD) models for an object. In such cases, high LOD (complex) objects are replaced with lower LOD (simple) objects when objects are “far away” from the viewing plane. Because the lower LOD objects are geometrically simpler than the high LOD objects, the rendering engine generally performs fewer calculations. Accordingly, the rendering process is expected to be improved.
One drawback to the LOD technique has been that when transitioning between a high LOD model to a low LOD model, undesirable visual artifacts appear. As an example, because the high LOD model and the lower LOD model are geometrically different, surfaces of the object rendered in different images may have different surface normals, and the like. Although such artifacts may not be visible on an individual image, when a viewer views images consecutively, such as when watching a feature, the artifacts appear as distracting “sparkles” or “pops” to a viewer.
One solution developed by Pixar engineers to reduce the undesirable artifacts of LOD transitions was described in U.S. Pat. No. 6,300,956. In this patent, to provide a smoother transition between LOD models, stochastic sampling techniques were introduced on a pixel-by-pixel basis to determine which of the LOD models contributes to the final image. Stochastic (pseudo-random) sampling techniques was first invented for use in computer animation by the named inventor of the present invention, and is described in U.S. Pat. No. 4,897,806, assigned to Pixar.
Another drawback to the LOD techniques has been that it requires a manual definition of the different LOD models for the object. In some cases, three or more different LOD models must be manually designed. Definition of these different LOD models is very time consuming, especially when the object is complex.
Some techniques have been described that provide for formation of one LOD model based upon another LOD model. One technique typically relies upon selective removal or replacement of vertices from surface descriptions in a high LOD model to form a lower LOD model.
Drawbacks to the LOD surface simplification approach include that such computations are extremely time consuming when processing typical computer animation models. For example, procedurally created models for computer animation may include millions of geometric elements, each of which could be simplified according to the above techniques. Another drawback to such techniques includes that LOD simplifications are typically directed to simplification via removal of vertices from an object and not via removal of higher-level geometric elements of an object, e.g. leaves, hair. Yet another drawback includes that when a vertex is removed using LOD simplification, the techniques fail to consider the effect of simplification on the over-all properties of the object, e.g. surface area, contrast, etc.
Accordingly, what is desired are improved methods and apparatus for solving the problems discussed above, while reducing the drawbacks discussed above.